大數乘法


Posted by cwc329 on 2020-06-21

打完上一篇發現篇幅太長,想說拆成兩篇。
因為我自己也不太習慣閱讀長文章。

大數乘法

這題給的提示「直式乘法」讓這題變得很好理解,先用比較小的數字來看我們怎麼做直式乘法的,ex: 12*34。
我們在做直式乘法會拆成:

(12\*4) + (12\*30)

這邊可以看出在一般的直式我們是把後面的數的每個位數拆開來去乘上前面的數,再把結果相加。
但是直接拿這個來解大數乘法 JS 會死給你看,因為前面的數超出安全整數,再乘下去也不會得到正確結果。
那要怎麼辦呢?我們可以把直式再拆更細來看,就會變成:

(4\*2) + (4\*10) + (30\*2) + (30\*10)

這邊用的直式乘法跟一般的不太一樣,我這邊直接把他拆成一次只處理一個位數。
再仔細觀察每個括號,由右開始數,在直式運算中前數的第 m 個數乘上後數的第 n 個數,其結果由右開始第一個 !== 0 的位置會是 m + n - 1,這個對我解題很重要,詳細的後面會說。
找到乘法的運算規律後,就繼續請出我的好朋友陣列。
先把兩個字串的每個字切割並且轉換成陣列並且將元素轉為數字 String.split('').map(Number),再來就是設定儲存結果的變數 result = []
result 一開始我就設定是個二維陣列,拿來儲存答案每個位數的數字,為了方便,我先在裡面放好需要用的陣列 [0]
那要多少個呢?我按了按計算機(真的沒有唬爛),發現 x 位數 * y 位數的答案會介於 x + y 與 x + y - 1 之間,我就先把 result 裡面放兩個字串長度和個 [0]。
接下來就是用 for 的雙層迴圈來跑直式乘法,至於為甚麼要用雙層迴圈,可以用印九九乘法表的概念來想。
這邊我是用遞減迴圈來跑,用來操作直式運算比較好用,也比較方便儲存位數。
得到位數相乘的結果後,剛剛說的 m + n - 1 就派上用場了。
因為每次只取一個位數處理,結果不會超過 81。
得到的個位數就把 push 到 result[m + n - 1],十位數就 push 到 result[m + n]。
當乘法運算結束後,result 會變成一個二維陣列,每個陣列中都有若干數字。
接著就是處理加法的部分,從最後面的陣列開始加總 Array.reduce((a, b) => a + b),加總的各位數取代掉當前陣列在 result 中的位置,其餘位數就 push 進他們該去的其他陣列。
就這樣從最後開始處理把 result 處理完,result 就變成一個一維陣列。
因為最後要轉成字串輸出,要注意第一個字是不是 0,如果 result 第一個元素是 0 就拿掉。
最後再用 Array.join('')就可以得到答案了。
我的這個解法不是最好的,可能挺不過超級大數字的壓力測試,不過我還是初心者而已,壓力測試不過又怎樣。
我的程式碼










Related Posts

What is the concept of handle in Java?

What is the concept of handle in Java?

Spring boot系列(六)Log

Spring boot系列(六)Log

The prototype chain in JavaScript

The prototype chain in JavaScript


Comments